package Other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class leet_42 {
    public static void main(String[] args) {
        Solution_42 p = new Solution_42();
        int[] height = new int[]{4,2,0,3,2,5};
        int result = p.trap(height);
        System.out.println(result);
    }
}

class Solution_42 {
    public int trap(int[] height) {
        int allWaterNum = dullStack(height);
        return allWaterNum;
    }

    /**
     * 利用双指针逻辑来计算
     * 除开首位与末尾根本没办法接住雨水
     * 其余位置接住雨水的数量与其前后最大
     * 高度与本身的差值是有关系的
     * @param height  柱子的高度数组
     * @return  能接的水滴数
     */
    public int DoubleLinkTrap(int[] height){
        if(height.length<3){
            return 0;
        }
        List<Integer> result = new ArrayList<>();
        // 首与尾没办法接住雨水所以不慌
        for(int i=1; i<height.length-1; i++){
            // 左边最大的值
            int maxLeft = 0;
            // 右边最大的值
            int maxRight = 0;
            // 左指针 找左边最大的值
            for(int left=0; left!=i; left++){
                int tmpNum = height[left];
                if(tmpNum > maxLeft){
                    maxLeft = tmpNum;
                }
            }
            // 右指针 找右边最大的值
            for(int right = height.length-1; right!=i; right--){
                int tmpNum = height[right];
                if(tmpNum > maxRight){
                    maxRight = tmpNum;
                }
            }
            // 左右2边最大里面最小的数据
            int maxMinNum = Math.min(maxLeft, maxRight);
            // 接水滴的量 为2边最高的里面最小的高度 减去本身的高度就是接的水滴
            int waterNum = maxMinNum - height[i];
            if(waterNum > 0){
                result.add(waterNum);
            }
        }
        int allWaterNum=0;
        for(int i=0; i<result.size(); i++){
            allWaterNum = allWaterNum + result.get(i);
        }
        return allWaterNum;
    }


    /**
     * 动态规划
     * 每个位置都是需要考虑前面的高度与后面的高度的
     * 把这个双重考虑拆解
     * 1.该点左边最长 - 本身高度接到的水
     * 2.该点右边最长 - 本身高度接到的水
     * 如果 左边高于右边的话，先考虑右边
     * 此时马上得到一个思想优先考虑接到水少的作为结果
     * @param height
     * @return
     */
    public int dynamicProgramming(int[] height){
        // 对左边进行动归
        int[] numsLeft = new int[height.length];
        int maxLeftNum = 0;
        for(int i=0; i<height.length; i++){
            int tmp = height[i];
            maxLeftNum = Math.max(maxLeftNum, tmp);
            // 这个位置的水滴数
            int waterNum = maxLeftNum - tmp;
            numsLeft[i] = waterNum;
        }

        // 对右进行动归
        int[] numsRight = new int[height.length];
        int maxRightNum = 0;
        for(int i=height.length-1; i>=0; i--){
            int tmp = height[i];
            maxRightNum = Math.max(maxRightNum, tmp);
            // 水滴数
            int waterNum = maxRightNum - tmp;
            numsRight[i] = waterNum;
        }

        int allWaterNum = 0;
        // 左右2边最小的做为最终的水滴
        for(int i=0; i<height.length; i++){
            int left = numsLeft[i];
            int right = numsRight[i];
            int tmpNum = Math.min(left, right);
            if(tmpNum>0){
                allWaterNum = allWaterNum + tmpNum;
            }
        }
        return allWaterNum;
    }


    /**
     * 单调栈
     * 什么是形成积水的条件 必须当前位置左边与右边有个高度差
     * 形成多少，长*宽
     * 宽：2边形成高度差的坐标之差-1 长：2边高度较小的与我本身的高度差
     * 此时解题思路出现了
     * @param height
     * @return
     */
    public int dullStack(int[] height){
        // 雨水总量
        int allWater = 0;
        // 记录栈(单调递减栈)
        Stack<Integer> stack = new Stack<>();
        // 循环整个
        for(int i=0; i<height.length; i++){
            int tmpNum = height[i];
            // 当前元素大于前面元素才可能存在低洼
            // 否则直接入栈
            while(!stack.isEmpty() && tmpNum>height[stack.peek()]){
                // 首先查看低洼情况(栈顶为低洼)
                int lyingIndex = stack.pop();
                // 这里需要尝试stack在抛出一个左边界
                // 如果不存在左边界直接返回继续
                if(stack.isEmpty()){
                    // 跳出当前while循环 当前边界值入栈 开始下一次for循环
                    break;
                }
                int leftIndex = stack.peek();
                // 记录当前积水坑左边与右边的情况下能积的水量
                int minNum = Math.min(height[leftIndex], tmpNum);
                // 长度
                int puddleLength = minNum - height[lyingIndex];
                // 宽
                int puddleWide = i-leftIndex-1;
                // 最后接的水
                int lyingWater = puddleLength * puddleWide;
                allWater = allWater + lyingWater;
            }
            // 直接入栈
            stack.push(i);
        }
        return allWater;
    }

}
